package 分治算法;

public class 汉诺塔 {
	public static void main(String[] args) {
		
		
		Hanota hanota = new Hanota();
		hanota.hanota(3, 'A', 'B', 'C');
		
		//hanota.hanota2(4, 'A', 'B', 'C');
	}
}

/**
 * 汉诺塔
 * @author PC
 *
 */
class Hanota {
	
	//次数
	int time;
	
	/**
	 * 汉诺塔算法  注意看参数的意义，容易理解
	 * @param num 层数/盘子
	 * @param a 塔 起始
	 * @param b 塔 辅助/绕过
	 * @param c 塔 终点
	 */
	public void hanota(int num, char a, char b, char c) {
		
		//如果只有一个盘
		if(num == 1) {
			//直接从A塔移动到C塔
			System.out.println("第1个盘从 " + a + "->" + c + "：第"+(++time)+"步");
		}else {
			//不止一个盘
			//1. 把剩下的盘分成两部分，第n个和剩下的n-1个，将n-1个从A到B，其中用到C
			hanota(num-1, a, c, b);
			
			//2. 把最下面一个从A到C，和上面那个num=1一样
			//最大的那个盘子可以无视，因为它只要放在最后一个，相等于没有盘子，其他随便盘子都可以放到它上面
			System.out.println("第" + num + "个盘从 " + a + "->" + c + "：第"+(++time)+"步");
			
			//3. 再把B上面的n-1个移到C上，使用到A
			hanota(num-1, b, a, c);
			
		}
	}
	
	/**
	 * 方法二 ：另外一种角度
	 * 移动盘子
	 * @param num
	 * @param a
	 * @param b
	 * @param c
	 */
	public void move(int num, char a, char b) {
		System.out.println("第1个盘从 " + a + "->" + b + "第："+(++time)+"步");
	}
	public void hanota2(int num, char a, char b, char c) {
		//如果只有一个盘
		if(num == 1) {
			move(num, a, c);
		}else {
			
			//移动上一关的步骤移动到B
			hanota(num-1, a, c, b);
			
			//把最大的盘子移动C塔	
			move(num, a, c);
			
			//再把B上的上一关的盘子移动到C上就可以了
			hanota(num-1, b, a, c);
			
		}
	}
}